package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/22 4:09 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1648 {

    public int maxProfit(int[] inventory, int orders) {
        int mod = 1000000007;
        long sum = 0;
        if (inventory.length == 1) {
            for (int i = 0; i < orders; i++) {
                sum += inventory[0];
                inventory[0] = inventory[0] -1;
            }
            if (sum > mod) {
                sum = sum % mod;
            }
            return (int)sum;
        }

        for (int i = inventory.length - 1; i >= 0; i--) {
            heapify(inventory, i, inventory.length);
        }

        for (int i = 0; i < orders; i++) {
            sum += inventory[0];
            inventory[0] = inventory[0] -1;
            heapify(inventory,0, inventory.length);
        }
        if (sum > mod) {
            sum = sum % mod;
        }
        return (int)sum;
    }


    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    public static void main(String[] args) {
        LeetCode1648 leetCode1648 = new LeetCode1648();

        int[] inventory = new int[]{2,5}; int orders = 4;
        System.out.println(leetCode1648.maxProfit(inventory, orders));


        int[] inventory2 = new int[]{3,5};
        int orders2 = 6;
        System.out.println(leetCode1648.maxProfit(inventory2, orders2));


       int[] inventory3 = new int[]{2,8,4,10,6};
       int orders3 = 20;
       System.out.println(leetCode1648.maxProfit(inventory3, orders3));


        int[] inventory5 = new int[]{1000000000};
        int orders5 = 1000000000;
        System.out.println(leetCode1648.maxProfit(inventory5, orders5));


        int[] inventory6 = new int[]{497978859, 167261111, 483575207, 591815159};
        int orders6 = 836556809;

        System.out.println(leetCode1648.maxProfit(inventory6, orders6));


    }
}
